package algorithm;

public class leetcode_0673 {
    public int findNumberOfLIS(int[] nums) {
        int len=nums.length;
        int[] count=new int[len];
        int[] dp=new int[len];
        int max=1;
        for(int i=0;i<len;++i){
            count[i]=1;
            dp[i]=1;
        }
        for(int i=1;i<len;++i){
            for(int j=0;j<i;++j){
                if(nums[i]>nums[j]){
                    if(dp[j]+1>dp[i]){
                        max=Math.max(dp[j]+1,max);
                        dp[i]=dp[j]+1;
                        count[i]=count[j];
                    }
                    else if(dp[j]+1==dp[i]){
                        count[i]+=count[j];
                    }
                }
            }
        }
        int result=0;
        for(int i=0;i<len;++i){
            if(dp[i]==max){
                result+=count[i];
            }
        }
        return result;
    }
}
